package leecode

import (
	"sort"
)

func findItinerary(tickets [][]string) []string {
	var (
		//每个起点对应的终点数组
		m   = map[string][]string{}
		res []string
	)

	// 初始化, 把图的邻接表存进字典
	for _, ticket := range tickets {
		src, dst := ticket[0], ticket[1]
		m[src] = append(m[src], dst)
	}
	// 按字典序排序
	for key := range m {
		sort.Strings(m[key])
	}

	// 从‘JFK’开始深搜，每前进一层就减去一条路径，直到某个起点不存在路径的时候就会跳出 循环进行回溯
	// 相对先找不到路径的一定是放在相对后面
	// 所以当前搜索的起点from会插在当前输出路径的第一个位置
	var dfs func(curr string)
	dfs = func(curr string) {
		for {
			// 这个起点终点已经走完了，或者是个死胡同没有回去的路
			if v, ok := m[curr]; !ok || len(v) == 0 {
				break
			}
			// 还有路继续走
			tmp := m[curr][0]
			// 去掉这个路
			m[curr] = m[curr][1:]
			dfs(tmp)
		}
		// 往下递归到终点之后开始入栈
		// 往上递归返回的入栈就是来时的路反着走回去，这样得到的数组是 路径的倒序
		// 越在链路后面的先入栈
		res = append(res, curr)
	}

	dfs("JFK")
	// 翻转数组
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

//type Tickets [][]string
//
//func (t Tickets) Len() int {
//	//TODO implement me
//	return len(t)
//}
//
//func (t Tickets) Less(i, j int) bool {
//	//TODO implement me
//	if t[i][0] == t[j][0] {
//		// 如果出发地相等 按照目的地排序
//		return t[i][1] < t[j][1]
//	}
//	return t[i][0] < t[j][0]
//}
//
//func (t Tickets) Swap(i, j int) {
//	//TODO implement me
//	t[i], t[j] = t[j], t[i]
//}
//
//func findItinerary(tickets [][]string) (result []string) {
//	sort.Sort(Tickets(tickets))
//	path := make([]string, 0, len(tickets)+1)
//	var bakctracking func(start string, used []bool)
//	bakctracking = func(start string, used []bool) {
//		if len(result) > 0 {
//			return
//		}
//		if len(path) == len(tickets)+1 {
//			result = append(result, path...)
//			return
//		}
//		for i := 0; i < len(tickets); i++ {
//			if used[i] || tickets[i][0] != start {
//				//如果当前票被使用 或者 这一张票的出发地不是上一张票的目的地
//				continue
//			}
//			used[i] = true
//			path = append(path, tickets[i][1]) //当前出发地的目的地
//			//下一次的出发地是这一次的目的地
//			bakctracking(tickets[i][1], used)
//			used[i] = false
//		}
//	}
//	used := make([]bool, len(tickets))
//	bakctracking("JFK", used)
//	return
//}
